{$R-,F-}(* This program finds all 92 positions of 8 queens on a cherssboard *)
(* such that no queen checks another queen.  The backtracking       *)
(* algorithmn is recursive.                                         *)

(* Run-time on the CDC 6400: 1017 msec. (679 msec without range checking)*)

PROGRAM EIGHTQUEENS(OUTPUT);
VAR I, q, iterations : INTEGER;
    SAFE: BOOLEAN;
    A : ARRAY[1..8] OF BOOLEAN;
    B : ARRAY[2..16] OF BOOLEAN;
    C : ARRAY[-7..7] OF BOOLEAN;
    X : ARRAY[1..8] OF INTEGER;
    
    SHITIME ,SLOWTIME, EHITIME, ELOWTIME: INTEGER;
   
Procedure Print;
  Var k: integer;
Begin
for k := 1 to 8 do (*
Write (x[k]: 2);
Writeln; *)
End;


PROCEDURE TRYCOL(J : INTEGER);
   VAR I : INTEGER; 
   
   PROCEDURE SETQUEEN;
   BEGIN A[I] := FALSE;  B[I+J] := FALSE;  C[I-J] := FALSE;
   END;
   
   PROCEDURE REMOVEQUEEN;
   BEGIN  A[I] := TRUE;  B[I+J] := TRUE;  C[I-J] := TRUE
   END;
BEGIN
   I:=0;
   REPEAT I := I+1;  SAFE := A[I] AND B[I+J] AND C[I-J];
      IF SAFE THEN 
      BEGIN  SETQUEEN;  X[J] := I;
         IF J < 8 THEN TRYCOL(J+1) ELSE PRINT;
         REMOVEQUEEN
      END
   UNTIL I = 8
END;

BEGIN   FOR I := 1 TO 8 DO A[I] := TRUE;
        FOR I := 2 TO 16 DO B[I] := TRUE;
        FOR I := -7 TO 7 DO C[I] := TRUE;
        
   Writeln;
   Writeln ('8 queens  (R-)');
   WRITE('Iterations ?  (<cr> starts benchmark) ');
   READLN (iterations);
     for q := 1 to iterations do begin
     (*
     Page (output);
     *)
     TRYCOL(1);  
     end;
   WRITELN('DONE', CHR (7));
END.
